package 二分法;

import java.util.Arrays;

public class searchMatrix240 {
    int len;
    int row;

    /**
     * 这是的使用的简单的二分法
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        len = matrix.length;
        if (len <= 0) {
            return false;
        }
        row = matrix[0].length;
        for (int[] arr : matrix) {
            if (Arrays.binarySearch(arr, target) >= 0) {
                return true;
            }
        }
        return false;
    }

    /**
     * 从左下角有着是右上角来实现的
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrixV2(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int x = 0, y = n - 1;
        // 从右边上角开始
        while (x < m && y >= 0) {
            // 如果相等于话
            if (matrix[x][y] == target) {
                return true;
            }
            // 如果表示的当前是大于的目标是 那么值就是y-1
            if (matrix[x][y] > target) {
                --y;
            } else {
                // 如果当前值小于目标值 那就判断在下面的元素 x+1
                ++x;
            }
        }
        return false;
    }
}
